package arrAndstr;

/*
    274. H 指数
 */
public class T274 {

    public static void main(String[] args) {
        int[] array = new int[]{3,0,6,1,5};

        System.out.println(hIndex(array));
    }


    public static int hIndex(int[] citations) {
        int len = citations.length;
        quickSort(citations, 0, len-1);
        int h = 0;

        for(int i=0; i<len; i++) {
            int temp = citations[i];
            if(temp > h) {
                int tempH = h+1;
                while(tempH <= temp) {
                    if(i+tempH <= len) {
                        h = tempH;
                    }
                    tempH++;
                }
            }
        }
        return h;
    }
    public static void quickSort(int[] array, int left, int right) {
        if(right-left <= 0) {
            return;
        }

        int leftIndex = left, rightIndex = right;
        int temp = array[leftIndex];

        while(leftIndex < rightIndex) {
            while(array[rightIndex] >= temp && leftIndex < rightIndex) {
                rightIndex--;
            }
            if(array[rightIndex] < temp && leftIndex < rightIndex) {
                array[leftIndex++] = array[rightIndex];
            }
            while(array[leftIndex] <= temp && leftIndex < rightIndex) {
                leftIndex++;
            }
            if(array[leftIndex] > temp && leftIndex < rightIndex) {
                array[rightIndex--] = array[leftIndex];
            }
        }
        array[leftIndex] = temp;

        quickSort(array, left, leftIndex-1);
        quickSort(array, leftIndex+1, right);
    }
}
